#pragma once
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>

namespace cr
{
    template <class T>
    struct ListNode
    {
    public:
        ListNode(const T &val = T())
            : _val(val), _next(nullptr), _pre(nullptr)
        {
        }

    public:
        T _val;
        ListNode *_next;
        ListNode *_pre;
    };

    template <class T, class ref, class ptr>
    class __iterator
    {
    public:
        typedef ListNode<T> Node;
        using Self = __iterator<T, ref, ptr>; // 规范写法，仅类内部可以省略模版参数

        // 反向迭代器使用
        typedef ref rref;
        typedef ptr rptr;

    public:
        Node *_node;

    public:
        __iterator(Node *node = nullptr)
            : _node(node)
        {
        }
        ref operator*()
        {
            return _node->_val;
        }
        ptr operator->()
        {
            return &_node->_val;
        }
        Self operator++(int) // 后置
        {
            Self tmp(_node);
            _node = _node->_next;
            return tmp;
        }
        Self &operator++() // 前置
        {
            _node = _node->_next;
            return *this;
        }

        Self operator--(int) // 后置
        {
            Self tmp(_node);
            _node = _node->_pre;
            return tmp;
        }
        Self &operator--() // 前置
        {
            _node = _node->_pre;
            return *this;
        }
        bool operator!=(const Self &it)
        {
            return _node != it._node;
        }
        bool operator==(const Self &it)
        {
            return _node == it._node;
        }
    };

    template <class iterator>
    class __reverse_iterator
    {
        typedef __reverse_iterator<iterator> Self;
        typedef typename iterator::rref ref;
        typedef typename iterator::rptr ptr;

    public:
        __reverse_iterator(const iterator &it)
            : _it(it) {}

        ref operator*()
        {
            return *_it;
        }
        ptr operator->()
        {
            return _it.operator->();
        }
        Self operator++(int) // 后置
        {
            return _it--;
        }
        Self operator++() // 前置
        {
            return --_it;
        }

        Self operator--(int) // 后置
        {
            return _it++;
        }
        Self operator--() // 前置
        {
            return --_it;
        }
        bool operator!=(const Self &rit)
        {
            return _it != rit._it;
        }
        bool operator==(const Self &rit)
        {
            return _it == rit._it;
        }

    private:
        iterator _it;
    };

    template <class T>
    class List
    {
        typedef ListNode<T> Node;

        typedef __iterator<T, T &, T *> iterator;
        typedef __iterator<T, const T &, const T *> const_iterator;
        typedef __reverse_iterator<iterator> reverse_iterator;
        typedef __reverse_iterator<const_iterator> const_reverse_iterator;

    public:
        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        const_iterator cbegin() const
        {
            return const_iterator(_head->_next);
        }
        const_iterator cend() const
        {
            return const_iterator(_head);
        }

        reverse_iterator rbegin()
        {
            return reverse_iterator(_head->_pre);
        }
        reverse_iterator rend()
        {
            return reverse_iterator(_head);
        }
        const_reverse_iterator crbegin() const
        {
            return const_reverse_iterator(_head->_pre);
        }
        const_reverse_iterator crend() const
        {
            return const_reverse_iterator(_head);
        }

        void creat_head()
        {
            if (_head)
                return;
            _head = new Node(); // 初始构造带头空节点
            _head->_next = _head->_pre = _head;
        }

    public:
        List()
        {
            creat_head();
        }
        List(int n, const T &val)
        {
            assert(n > 0);
            creat_head();
            while (n--)
                push_back(val);
        }

        template <class Iterator>
        List(Iterator first, Iterator last) // list<type> l(10,3);也会匹配这里
        {
            creat_head();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        List(const List &tmp)
        {
            creat_head();
            List temp(tmp.cbegin(), tmp.cend());
            swap(temp);
        }
        List &operator=(List tmp) // tmp接收参数会进行拷贝构造
        {
            this->swap(tmp);
            return *this;
        }

        void swap(List &tmp)
        {
            std::swap(_head, tmp._head);
        }

        ~List()
        {
            clear();
        }
        void push_back(const T &val)
        {
            Node *newnode = new Node(val);
            newnode->_pre = _head->_pre;
            newnode->_next = _head;
            _head->_pre->_next = newnode;
            _head->_pre = newnode;
        }
        template <class... Args>
        void emplace_back(Args &&...args)
        {
            Node *newnode = new Node();
            // 使用定位new在指定地址处进行构造
            new (newnode) T(std::forward<Args>(args)...);
            newnode->pre = _head->_pre;
            newnode->_next = _head;
            _head->_pre->_next = newnode;
            _head->_pre = newnode;
        }
        void push_front(const T &val)
        {
            Node *newnode = new Node(val);
            newnode->_pre = _head;
            newnode->_next = _head->_next;
            _head->_next->_pre = newnode;
            _head->_next = newnode;
        }
        template <class... Args>
        void emplace_front(Args &&...args)
        {
            Node *newnode = new Node();
            // 使用定位new在指定地址处进行构造
            new (newnode) T(std::forward<Args>(args)...);
            newnode->pre = _head;
            newnode->_next = _head->_next;
            _head->_next->_pre = newnode;
            _head->_next = newnode;
        }

        // 在pos位置前插入节点
        iterator insert(iterator pos, const T &val)
        {
            Node *newnode = new Node(val);
            Node *_pos = pos._node;
            newnode->_next = _pos;
            newnode->_pre = _pos->_pre;
            _pos->_pre->_next = newnode;
            _pos->_pre = newnode;

            return iterator(newnode);
        }

        void pop_back()
        {
            Node *del = _head->_pre;
            _head->_pre = _head->_pre->_pre;
            _head->_pre->_next = _head;
            delete del;
        }
        void pop_front()
        {
            Node *del = _head->_next;
            _head->_next = _head->_next->_next;
            _head->_next->_pre = _head;
            delete del;
        }
        iterator erase(iterator pos)
        {
            Node *_pos = pos._node;
            Node *pre = _pos->_pre;
            Node *next = _pos->_next;
            delete _pos;
            pre->_next = next;
            next->_pre = pre;

            return iterator(next);
        }

        T &front()
        {
            return _head->_next->_val;
        }
        const T &front() const
        {
            return _head->_next->_val;
        }
        T &back()
        {
            return _head->_pre->_val;
        }
        const T &back() const
        {
            return _head->_pre->_val;
        }

        size_t size()
        {
            size_t count = 0;
            Node *cur = _head->_next;
            while (cur != _head)
            {
                cur = cur->_next;
                count++;
            }
            return count;
        }

        void clear()
        {
            Node *cur = _head->_next;
            Node *tail;
            while (cur != _head)
            {
                tail = cur->_next;
                delete cur;
                cur = tail;
            }
            delete _head;
            _head = nullptr;
        }

    private:
        Node *_head = nullptr; // 带头空节点
    };

    template <class T>
    std::ostream &operator<<(std::ostream &out, List<T> &tmp)
    {
        // 当前实现若遇到const修饰的List对象无法正确的调用cbegin
        for (auto it : tmp)
        {
            std::cout << it << ' ';
        }
        return out;
    }
}